package com.javaDemo.ti;

import java.util.Arrays;

/**
 * @ClassName: Sort
 * @Auther: csy
 * @Date: 2020/4/5 15:07
 * @Description:
 */
public class Sort {
    static int[] init={3,2,1,4,7,8};


    public static void main(String[] args) {
        // System.out.println(insertSort(init));
        //  Arrays.stream(shellSort(init)).forEach(target-> System.out.println(target));
        //  System.out.println(shellSort1(init));
         System.out.println(shellSort(init));
        //   System.out.println(GuibinpaixuSort(init));

    }
    /**
     * 希尔排序 针对有序序列在插入时采用交换法
     * @param arr
     */
    public static int[] shellSort(int[] arr){
        //增量gap，并逐步缩小增量
        for(int gap=arr.length/2;gap>0;gap/=2){
            //从第gap个元素，逐个对其所在组进行直接插入排序操作
            for(int i=gap;i<arr.length;i++){
                int j = i;
                while(j-gap>=0 && arr[j]<arr[j-gap]){
                    //插入排序采用交换法
                    swap(arr,j,j-gap);
                    j-=gap;
                }
            }
        }
        return arr;
    }

    /**
     * 希尔排序 针对有序序列在插入时采用移动法。
     * @param arr
     */
    public static int[] shellSort1(int []arr){
        //增量gap，并逐步缩小增量
        for(int gap=arr.length/2;gap>0;gap/=2){
            //从第gap个元素，逐个对其所在组进行直接插入排序操作
            for(int i=gap;i<arr.length;i++){
                int j = i;
                int temp = arr[j];
                if(arr[j]<arr[j-gap]){
                    while(j-gap>=0 && temp<arr[j-gap]){
                        //移动法
                        arr[j] = arr[j-gap];
                        j-=gap;
                    }
                    arr[j] = temp;
                }
            }
        }
        return  arr;
    }

    /**
     * 交换数组元素
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int []arr,int a,int b){
        arr[a] = arr[a]+arr[b];
        arr[b] = arr[a]-arr[b];
        arr[a] = arr[a]-arr[b];
    }

    public static int[] insertSort1(int[] init){
        if(init.length==0){
            return null;
        }
        int c;
        for(int i=0;i<init.length-1;i++){
            c=init[i+1];
            int page=i;
            while(page>=0&&c<init[page]){
                init[page+1]=init[page];
                page--;
            }
            init[page+1]=c;
        }
        return init;
    }

    /**
     * 插入排序
     * @param array
     * @return
     */
    public static int[] insertionSort(int[] array) {
        if (array.length == 0)
            return array;
        int current;
        for (int i = 0; i < array.length - 1; i++) {
            current = array[i + 1];
            int preIndex = i;
            while (preIndex >= 0 && current < array[preIndex]) {
                array[preIndex + 1] = array[preIndex];
                preIndex--;
            }
            array[preIndex + 1] = current;
        }
        return array;
    }


    public static int[] boboSort(int[] a){
        if(a.length==0){
            return null;
        }
        for(int i=0;i<a.length;i++){
            for(int j=0;j<a.length-1-i;j++){
                if(a[j+1]<a[j]){
                    int temp=a[j+1];
                    a[j+1]=a[j];
                    a[j]=temp;
                }
            }
        }
        return a;
    }

    // /**
    //  * 冒泡排序
    //  *
    //  * @param array
    //  * @return
    //  */
    // public static int[] bubbleSort(int[] array) {
    //     if (array.length == 0) {
    //         return array;
    //     }
    //     for (int i = 0; i < array.length; i++) {
    //         for (int j = 0; j < array.length - 1 - i; j++) {
    //             if (array[j + 1] < array[j]) {
    //                 int temp = array[j + 1];
    //                 array[j + 1] = array[j];
    //                 array[j] = temp;
    //             }
    //         }
    //     }
    //     return array;
    // }

    /**
     * 选择排序
     * @param array
     * @return
     */
    public static int[] selectionSort(int[] array) {
        if (array.length == 0) {
            return array;
        }
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i; j < array.length; j++) {
                if (array[j] < array[minIndex])  { //找到最小的数
                    minIndex = j; //将最小数的索引保存
                }
            }
            int temp = array[minIndex];
            array[minIndex] = array[i];
            array[i] = temp;
        }
        return array;
    }

    /**
     * 归并排序
     *
     * @param array
     * @return
     */
    public static int[] MergeSort(int[] array) {
        if (array.length < 2) return array;
        int mid = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        return merge(MergeSort(left), MergeSort(right));
    }
    /**
     * 归并排序——将两段排序好的数组结合成一个排序数组
     *
     * @param left
     * @param right
     * @return static int[] init={12,1,14,123,144,25,46,13,17,33};
     */
    public static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        for (int index = 0, i = 0, j = 0; index < result.length; index++) {
            if (i >= left.length)
                result[index] = right[j++];
            else if (j >= right.length)
                result[index] = left[i++];
            else if (left[i] > right[j])
                result[index] = right[j++];
            else
                result[index] = left[i++];
        }
        return result;
    }



}
